package pl.mmadej.ds4java.ds.tree.binary.bst;


import pl.mmadej.ds4java.ds.common.DataStructure;
import pl.mmadej.ds4java.ds.queue.LinkedListQueue;
import pl.mmadej.ds4java.ds.queue.Queue;
import pl.mmadej.ds4java.ds.stack.ArrayStack;
import pl.mmadej.ds4java.ds.stack.Stack;
import pl.mmadej.ds4java.ds.tree.binary.BinaryTree;
import pl.mmadej.ds4java.ds.tree.binary.BinaryTreeNode;

public class BinarySearchTree<T extends Comparable<T>> extends DataStructure<T> implements BinaryTree<T> {

    protected BinaryTreeNode<T> root;

    private int noOfElements;

    @Override
    public final boolean insert(T value) {
        BinaryTreeNode<T> newNode = new BinaryTreeNode<T>(value);
        FindNodeHelper findNodeHelperForGivenValue = new FindNodeHelper(value);
        findNodeHelperForGivenValue.tryToFindInTheTree();
        if (findNodeHelperForGivenValue.wasNotFound()) {
            BinaryTreeNode<T> parentOfNewNode = findNodeHelperForGivenValue.potentialParent();
            insertNewElementUnderParent(newNode, parentOfNewNode);
            afterNodeAdded(newNode);
            noOfElements++;
        } else {
            afterNodeAccessed(findNodeHelperForGivenValue.foundNode());
        }
        return findNodeHelperForGivenValue.wasNotFound();
    }

    @Override
    public final boolean contains(T value) {
        FindNodeHelper findNodeHelperForGivenValue = new FindNodeHelper(value);
        findNodeHelperForGivenValue.tryToFindInTheTree();
        if (findNodeHelperForGivenValue.wasFound()) {
            afterNodeAccessed(findNodeHelperForGivenValue.foundNode());
        } else {
            afterNodeAccessed(findNodeHelperForGivenValue.potentialParent());
        }
        return findNodeHelperForGivenValue.wasFound();
    }

    @Override
    public final boolean delete(T value) {
        FindNodeHelper findNodeHelperForGivenValue = new FindNodeHelper(value);
        findNodeHelperForGivenValue.tryToFindInTheTree();
        if (findNodeHelperForGivenValue.wasFound()) {
            deleteNode(findNodeHelperForGivenValue.foundNode());
        }
        return findNodeHelperForGivenValue.wasFound();
    }

    @Override
    public final int numberOfElements() {
        return noOfElements;
    }

    @Override
    @SuppressWarnings("unchecked")
    public final <E> E[] levelOrder(E[] resultArray) {
        resultArray = createArrayIfNeeded(resultArray,noOfElements);

        int index = 0;
        Queue<BinaryTreeNode<T>> nodeQueue = new LinkedListQueue<BinaryTreeNode<T>>();
        if (root != null) {
            nodeQueue.enqueue(root);
        }
        while (!nodeQueue.empty()) {
            BinaryTreeNode<T> node = nodeQueue.dequeue();
            resultArray[index++] = (E) node.getValue();
            if (node.getLeftChild() != null) {
                nodeQueue.enqueue(node.getLeftChild());
            }
            if (node.getRightChild() != null) {
                nodeQueue.enqueue(node.getRightChild());
            }
        }
        return resultArray;
    }

    @Override
    @SuppressWarnings("unchecked")
    public final <E> E[] preOrder(E[] resultArray) {
        resultArray = createArrayIfNeeded(resultArray,noOfElements);
        int index = 0;
        Stack<BinaryTreeNode<T>> stack = new ArrayStack<BinaryTreeNode<T>>(noOfElements);
        if (root != null) {
            stack.push(root);
        }
        while (!stack.empty()) {
            BinaryTreeNode<T> node = stack.pop();
            resultArray[index++] = (E) node.getValue();
            if (node.getRightChild() != null) {
                stack.push(node.getRightChild());
            }
            if (node.getLeftChild() != null) {
                stack.push(node.getLeftChild());
            }
        }
        return resultArray;
    }

    @Override
    @SuppressWarnings("unchecked")
    //using additional queue, maybe not so memory efficient but nice ;-)
    public final <E> E[] postOrder(E[] resultArray) {
        resultArray = createArrayIfNeeded(resultArray,noOfElements);
        Stack<T> values = new ArrayStack<T>(noOfElements);
        Stack<BinaryTreeNode<T>> stack = new ArrayStack<BinaryTreeNode<T>>(noOfElements);
        if (root != null) {
            stack.push(root);
        }
        while (!stack.empty()) {
            BinaryTreeNode<T> node = stack.pop();
            values.push(node.getValue());
            if (node.getLeftChild() != null) {
                stack.push(node.getLeftChild());
            }
            if (node.getRightChild() != null) {
                stack.push(node.getRightChild());
            }
        }
        int arrayIndex = 0;
        while (!values.empty()) {
            resultArray[arrayIndex++] = (E) values.pop();
        }
        return resultArray;
    }

    @Override
    @SuppressWarnings("unchecked")
    public final <E> E[] inOrder(E[] resultArray) {
        Stack<BinaryTreeNode<T>> stack = new ArrayStack<BinaryTreeNode<T>>(noOfElements);
        resultArray = createArrayIfNeeded(resultArray,noOfElements);
        int index = 0;
        BinaryTreeNode<T> node = root;
        while (true) {
            while (node != null) {
                stack.push(node);
                node = node.getLeftChild();
            }
            if (stack.empty()) {
                break;
            }
            node = stack.pop();
            resultArray[index++] = (E) node.getValue();
            node = node.getRightChild();
        }
        return resultArray;
    }

    protected final void rotateRight(BinaryTreeNode<T> nodeToGoDownOnRightSize) {
        BinaryTreeNode<T> leftChildOfNode = nodeToGoDownOnRightSize.getLeftChild();
        nodeToGoDownOnRightSize.setLeftChild(leftChildOfNode.getRightChild());
        if (leftChildOfNode.getRightChild() != null) {
            leftChildOfNode.getRightChild().setParent(nodeToGoDownOnRightSize);
        }
        leftChildOfNode.setParent(nodeToGoDownOnRightSize.getParent());
        nodeToGoDownOnRightSize.setParent(leftChildOfNode);
        leftChildOfNode.setRightChild(nodeToGoDownOnRightSize);
        updateParentOfNodeMovedUp(nodeToGoDownOnRightSize, leftChildOfNode);
        afterNodeRotatedRight(nodeToGoDownOnRightSize, leftChildOfNode);
    }

    protected final void rotateLeft(BinaryTreeNode<T> nodeToGoDownOnLeftSide) {
        BinaryTreeNode<T> rightChildOfNode = nodeToGoDownOnLeftSide.getRightChild();
        nodeToGoDownOnLeftSide.setRightChild(rightChildOfNode.getLeftChild());
        if (rightChildOfNode.getLeftChild() != null) {
            rightChildOfNode.getLeftChild().setParent(nodeToGoDownOnLeftSide);
        }
        rightChildOfNode.setParent(nodeToGoDownOnLeftSide.getParent());
        nodeToGoDownOnLeftSide.setParent(rightChildOfNode);
        rightChildOfNode.setLeftChild(nodeToGoDownOnLeftSide);
        updateParentOfNodeMovedUp(nodeToGoDownOnLeftSide, rightChildOfNode);
        afterNodeRotatedLeft(nodeToGoDownOnLeftSide, rightChildOfNode);
    }

    private void deleteNode(BinaryTreeNode<T> node) {
        BinaryTreeNode<T> nodeToTakePlaceOfDeletedNode = node.getLeftChild();
        nodeToTakePlaceOfDeletedNode = node.getRightChild() != null ? findAndCutFromTreeSuccessorNodeToTakePlaceOfDeletedNode(node) : nodeToTakePlaceOfDeletedNode;
        BinaryTreeNode<T> lowestAffectedNode = nodeToTakePlaceOfDeletedNode;
        updateParentNodeWithNewChild(node, nodeToTakePlaceOfDeletedNode);
        if (nodeToTakePlaceOfDeletedNode != null) {
            if (nodeToTakePlaceOfDeletedNode.getParent() != node) {
                lowestAffectedNode = nodeToTakePlaceOfDeletedNode.getParent();
            }
            nodeToTakePlaceOfDeletedNode.setParent(node.getParent());
        }
        if (lowestAffectedNode == null) {
            lowestAffectedNode = node.getParent();
        }
        nullNodeValueParentAndChildren(node);
        noOfElements--;
        if (lowestAffectedNode != null) {
            afterNodeDeleted(lowestAffectedNode);
        }
    }

    private void updateParentOfNodeMovedUp(BinaryTreeNode<T> nodeMovedDown, BinaryTreeNode<T> childMovedUp) {
        if (nodeMovedDown == root) {
            root = childMovedUp;
        } else if (childMovedUp.getParent().getLeftChild() == nodeMovedDown) {
            childMovedUp.getParent().setLeftChild(childMovedUp);
        } else {
            childMovedUp.getParent().setRightChild(childMovedUp);
        }
    }

    private void insertNewElementUnderParent(BinaryTreeNode<T> newNode, BinaryTreeNode<T> parentOfNewNode) {
        if (root == null) {
            root = newNode;
        } else if (newNode.getValue().compareTo(parentOfNewNode.getValue()) >= 0) {
            parentOfNewNode.setRightChild(newNode);
        } else {
            parentOfNewNode.setLeftChild(newNode);
        }
        newNode.setParent(parentOfNewNode);
    }

    private void nullNodeValueParentAndChildren(BinaryTreeNode<T> node) {
        node.setParent(null);
        node.setLeftChild(null);
        node.setRightChild(null);
    }

    private void updateParentNodeWithNewChild(BinaryTreeNode<T> node, BinaryTreeNode<T> nodeToTakePlaceOfDeletedNode) {
        if (node == root) {
            root = nodeToTakePlaceOfDeletedNode;
        } else {
            if (node.getParent().getLeftChild() == node) {
                node.getParent().setLeftChild(nodeToTakePlaceOfDeletedNode);
            } else {
                node.getParent().setRightChild(nodeToTakePlaceOfDeletedNode);
            }
        }
    }

    private BinaryTreeNode<T> findAndCutFromTreeSuccessorNodeToTakePlaceOfDeletedNode(BinaryTreeNode<T> node) {
        BinaryTreeNode<T> nodeToTakePlaceOfDeletedNode = successorNode(node);
        if (nodeToTakePlaceOfDeletedNode != node.getRightChild()) {
            nodeToTakePlaceOfDeletedNode.getParent().setLeftChild(nodeToTakePlaceOfDeletedNode.getRightChild());
            if (nodeToTakePlaceOfDeletedNode.getRightChild() != null) {
                nodeToTakePlaceOfDeletedNode.getRightChild().setParent(nodeToTakePlaceOfDeletedNode.getParent());
            }
        }
        setChildrenOfSuccessorNodeToTakePlaceOfDeletedNode(node, nodeToTakePlaceOfDeletedNode);
        return nodeToTakePlaceOfDeletedNode;
    }

    //private helpers
    private BinaryTreeNode<T> successorNode(BinaryTreeNode<T> node) {
        BinaryTreeNode<T> currentNode = node.getRightChild();
        BinaryTreeNode<T> nodeToReturn = node.getRightChild();
        while (currentNode != null) {
            nodeToReturn = currentNode;
            currentNode = currentNode.getLeftChild();
        }
        return nodeToReturn;
    }

    private void setChildrenOfSuccessorNodeToTakePlaceOfDeletedNode(BinaryTreeNode<T> node, BinaryTreeNode<T> nodeToTakePlaceOfDeletedNode) {
        nodeToTakePlaceOfDeletedNode.setLeftChild(node.getLeftChild());
        if (node.getLeftChild() != null) {
            node.getLeftChild().setParent(nodeToTakePlaceOfDeletedNode);
        }
        if (node.getRightChild() != nodeToTakePlaceOfDeletedNode) {
            nodeToTakePlaceOfDeletedNode.setRightChild(node.getRightChild());
            node.getRightChild().setParent(nodeToTakePlaceOfDeletedNode);
        }
    }

    private class FindNodeHelper {

        private T value;
        private BinaryTreeNode<T> potentialParent;
        private BinaryTreeNode<T> foundNode;

        private FindNodeHelper(T value) {
            this.value = value;
        }

        public BinaryTreeNode<T> potentialParent() {
            return potentialParent;
        }

        public BinaryTreeNode<T> foundNode() {
            return foundNode;
        }

        public boolean wasNotFound() {
            return foundNode == null;
        }

        public boolean wasFound() {
            return foundNode != null;
        }

        private void tryToFindInTheTree() {
            BinaryTreeNode<T> node = root;
            BinaryTreeNode<T> prev = root;
            while (node != null) {
                prev = node;
                if (node.getValue().equals(value)) {
                    foundNode = node;
                }
                if (value.compareTo(node.getValue()) >= 0) {
                    node = node.getRightChild();
                } else {
                    node = node.getLeftChild();
                }
            }
            potentialParent = prev;
        }
    }

    //event for subclasses
    protected void afterNodeAdded(BinaryTreeNode<T> newNode) {
        //empty for binary treeUnderTest
    }

    //event for subclass
    protected void afterNodeDeleted(BinaryTreeNode<T> lowestAffectedParent) {
        //empty for binary treeUnderTest
    }

    //event for subclass
    protected void afterNodeRotatedLeft(BinaryTreeNode<T> nodeToGoDownOnLeftSide, BinaryTreeNode<T> rightChildOfNode) {
        //empty for binary treeUnderTest
    }

    //event for subclass
    protected void afterNodeRotatedRight(BinaryTreeNode<T> nodeToGoDownOnRightSide, BinaryTreeNode<T> leftChildOfNode) {
        //empty for binary treeUnderTest
    }

    //event for subclass
    protected void afterNodeAccessed(BinaryTreeNode<T> accessedNode) {
        //empty for binary treeUnderTest
    }

}
